/*
 * Created by: Mark Lavrynenko
 * Email:	MarkLavrinenko@gmail.com
 * Project:	  Huffman
*/

#include "TreeBuilder.h"
#include "HTree.h"
#include "FrequencyTable.h"

HTree* TreeBuilder::buildTree(FrequencyTable* table)
{
	for (size_t i = 0; i < tableSize; ++i)
	{
		size_t count = table->countForByte(i);
		nodes[i] =  (count > 0) ?  new HuffmanTreeNode((uint8_t)i, count) : nullptr;
	}

	bool needNext = true;
	while (needNext = makeStep())
	{
		// do nothing
	}
	HuffmanTreeNode* root = nullptr;
	for (size_t i = 0; i < tableSize; ++i)
	{
		if (nullptr != nodes[i])
		{
			root = nodes[i];
			break;
		}
	}
	assert(nullptr != root);
	HTree* tree =  new HTree(root);
	return tree;
}

bool TreeBuilder::makeStep()
{
	size_t first = findMinPosition();
	size_t second = findMinPosition(first);
	if (notFound == first || notFound == second)
		return false;
	nodes[first] = new HuffmanTreeNode(nodes[first], nodes[second]);
	nodes[second] = nullptr;
	return true;	
}

size_t TreeBuilder::findMinPosition(size_t ignore)
{
	size_t ans = notFound;
	mytype maxAmount = MAX_FILE_LEN;
	for (size_t i = 0; i < tableSize; ++i)
	{
		if (ignore != i && nullptr != nodes[i] && nodes[i]->value < maxAmount)
		{
			maxAmount = nodes[i]->value;
			ans = i;
		}
	}
	return ans;
}